package 代码随想录_单调栈;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author zx
 * @create 2023-02-07 23:56
 */
public class 下一个更大元素II_503 {
    /**
     * 如何实现循环数组:
     * 循环数组就是说数组的最后一个元素下一个元素是数组的第一个元素,形状类似于[环]
     * 一种实现方式是把数组复制一份到数组末尾,这样虽然不是严格的循环数组,但是对于本题已经足够了,因为本题对数组最多遍历两次.
     * 另一个常见的实现方式是,使用取模运算%可以把下标 i 映射到数组nums长度的0 - N内。
     * @param nums
     * @return
     */
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        for(int i = 0;i < nums.length;i++){
            res[i] = -1;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < 2 * nums.length; i++) {
            while (!stack.isEmpty() && nums[i % nums.length] > nums[stack.peek()]) {
                res[stack.pop()] = nums[i % nums.length];
            }
            stack.push( i % nums.length);
        }
        return res;
    }
}
